package com.zhugang.week14.coding;


import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: test
 * @author: chanzhugang
 * @create: 2022/10/24 14:48
 */
public class PathSum {
    /**
     * 二叉树的路径总和
     */
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 递归
        if (root == null) {
            return result;
        }
        dfs(root, sum, new ArrayList<>(), 0);
        return null;
    }

    private void dfs(TreeNode root, int sum, List<Integer> path, int pathSum) {
        pathSum += root.val;
        path.add(root.val);
        if (root.left == null && root.right == null) {
            // 到了叶子节点
            // 回溯
            if (pathSum == sum) {
                // 一组解
                List<Integer> temp = new ArrayList<>();
                temp.addAll(path);
                result.add(temp);
            }
            path.remove(path.size() - 1);
            return;
        }
        if (root.left != null) {
            // 递归
            dfs(root.left, sum, path, pathSum);
        }
        if (root.right != null) {
            dfs(root.right, sum, path, pathSum);
        }
        path.remove(path.size() - 1);
    }

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


}